#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <float.h>
#include <assert.h>
#include <windows.h>

// 定义物品结构体
typedef struct {
    int id;
    int weight;
    double value;
    double ratio; // 价值/重量比
} Item;

// 比较函数：用于按价值/重量比降序排序
int compare_items(const void *a, const void *b) {
    Item *itemA = (Item *)a;
    Item *itemB = (Item *)b;
    return (itemB->ratio - itemA->ratio) > 0 ? 1 : -1;
}

// 蛮力法求解0-1背包问题
void brute_force(int n, int capacity, Item *items, clock_t *exec_time) {
    if (n > 20) {  // 安全限制，防止计算时间过长
        printf("n=%d 过大，蛮力法跳过执行\n", n);
        *exec_time = -1;
        return;
    }

    clock_t start = clock();
    
    double max_value = 0;
    unsigned long long best_combination = 0;
    unsigned long long total_combinations = 1ULL << n;
    
    // 遍历所有可能的物品组合（2^n种）
    for (unsigned long long mask = 0; mask < total_combinations; mask++) {
        int total_weight = 0;
        double total_value = 0;
        
        for (int i = 0; i < n; i++) {
            if (mask & (1ULL << i)) {
                total_weight += items[i].weight;
                total_value += items[i].value;
                // 提前终止：超重时跳过剩余物品
                if (total_weight > capacity) break;
            }
        }
        
        if (total_weight <= capacity && total_value > max_value) {
            max_value = total_value;
            best_combination = mask;
        }
    }
    
    clock_t end = clock();
    *exec_time = end - start;

    // 输出结果
    if (*exec_time != -1) {
        printf("\n蛮力法结果:\n");
        printf("最大价值: %.2f\n", max_value);
        printf("选择物品: ");
        for (int i = 0; i < n; i++) {
            if (best_combination & (1ULL << i)) {
                printf("%d ", items[i].id);
            }
        }
        printf("\n执行时间: %.2f ms\n", ((double)*exec_time)/CLOCKS_PER_SEC*1000);
    }
    
    printf("总价值: %d\n", max_value);
    printf("选择的物品编号: ");
    for (int i = 0; i < n; i++) {
        if (best_combination & (1 << i)) {
            printf("%d ", items[i].id);
        }
    }
    printf("\n执行时间: %.2f ms\n", ((double)*exec_time) / CLOCKS_PER_SEC * 1000);
}

// 动态规划法求解0-1背包问题（空间优化版）
void dynamic_programming(int n, int capacity, Item *items, clock_t *exec_time, long long *memory_usage) {
    clock_t start = clock();
    
    // 空间优化：使用一维数组
    int *dp = (int *)calloc(capacity + 1, sizeof(int));
    *memory_usage = (long long)(capacity + 1) * sizeof(int);
    printf("估计内存使用: %.2f MB\n", (double)*memory_usage / (1024 * 1024));
    
    // 填充动态规划表
    for (int i = 0; i < n; i++) {
        for (int w = capacity; w >= items[i].weight; w--) {
            if (dp[w - items[i].weight] + items[i].value > dp[w]) {
                dp[w] = dp[w - items[i].weight] + items[i].value;
            }
        }
    }
    
    int max_value = dp[capacity];
    clock_t end = clock();
    *exec_time = end - start;
    
    printf("总价值: %d\n", max_value);
    printf("选择的物品编号: ");
    // 输出具体选择的物品(以动态规划为例)
    int w = capacity;
    for (int i = n; i > 0 && w > 0; i--) {
        if (dp[w] != dp[w - items[i-1].weight] + items[i-1].value) {
            printf("%d ", items[i-1].id);
            w -= items[i-1].weight;
        }
    }
    printf("\n执行时间: %.2f ms\n", ((double)*exec_time) / CLOCKS_PER_SEC * 1000);
    
    free(dp);
}

// 贪心法求解0-1背包问题（注意：贪心法不能保证得到最优解）
void greedy(int n, int capacity, Item *items, clock_t *exec_time) {
    clock_t start = clock();
    
    // 计算每个物品的价值/重量比并排序
    for (int i = 0; i < n; i++) {
        items[i].ratio = (double)items[i].value / items[i].weight;
    }
    qsort(items, n, sizeof(Item), compare_items);
    
    int total_weight = 0;
    int total_value = 0;
    
    // 按比率从高到低选择物品
    for (int i = 0; i < n; i++) {
        if (total_weight + items[i].weight <= capacity) {
            total_weight += items[i].weight;
            total_value += items[i].value;
        }
    }
    
    clock_t end = clock();
    *exec_time = end - start;
    
    printf("总价值: %d\n", total_value);
    printf("选择的物品编号: ");
    for (int i = 0; i < n; i++) {
        if (total_weight >= items[i].weight) {
            printf("%d ", items[i].id);
            total_weight -= items[i].weight;
        }
    }
    printf("\n执行时间: %.2f ms\n", ((double)*exec_time) / CLOCKS_PER_SEC * 1000);
}

// 回溯法求解0-1背包问题（带剪枝优化）
typedef struct {
    int level;      // 当前处理的物品层级
    int profit;     // 当前价值
    int weight;     // 当前重量
    int bound;      // 价值上界
} Node;

// 计算节点的价值上界
int bound(Node u, int n, int capacity, Item *items) {
    if (u.weight >= capacity) {
        return 0;
    }
    
    int profit_bound = u.profit;
    int j = u.level + 1;
    int total_weight = u.weight;
    
    while (j < n && total_weight + items[j].weight <= capacity) {
        total_weight += items[j].weight;
        profit_bound += items[j].value;
        j++;
    }
    
    if (j < n) {
        profit_bound += (capacity - total_weight) * items[j].ratio;
    }
    
    return profit_bound;
}

// 回溯法求解0-1背包问题的辅助函数（迭代实现）
int backtracking(int n, int capacity, Item *items, clock_t *exec_time) {
    clock_t start = clock();
    
    // 按价值/重量比排序以优化剪枝
    for (int i = 0; i < n; i++) {
        items[i].ratio = (double)items[i].value / items[i].weight;
    }
    qsort(items, n, sizeof(Item), compare_items);
    
    int best_profit = 0;
    Node *stack = (Node *)malloc(n * sizeof(Node));
    int top = -1;
    
    // 初始化根节点
    Node root = {0, 0, 0, bound((Node){0, 0, 0, 0}, n, capacity, items)};
    stack[++top] = root;
    
    while (top >= 0) {
        Node current = stack[top--];
        
        // 如果当前节点的上界小于等于当前最优解，剪枝
        if (current.bound <= best_profit) {
            continue;
        }
        
        // 考虑选择当前层物品的情况
        if (current.weight + items[current.level].weight <= capacity) {
            int new_profit = current.profit + items[current.level].value;
            int new_weight = current.weight + items[current.level].weight;
            
            if (new_profit > best_profit) {
                best_profit = new_profit;
            }
            
            // 如果不是最后一层，继续扩展
            if (current.level + 1 < n) {
                Node left = {current.level + 1, new_profit, new_weight, 
                            bound((Node){current.level + 1, new_profit, new_weight, 0}, n, capacity, items)};
                if (left.bound > best_profit) {
                    stack[++top] = left;
                }
            }
        }
        
        // 考虑不选择当前层物品的情况
        if (current.level + 1 < n) {
            Node right = {current.level + 1, current.profit, current.weight, 
                         bound((Node){current.level + 1, current.profit, current.weight, 0}, n, capacity, items)};
            if (right.bound > best_profit) {
                stack[++top] = right;
            }
        }
    }
    
    clock_t end = clock();
    *exec_time = end - start;
    
    printf("总价值: %d\n", best_profit);
    printf("执行时间: %.2f ms\n", ((double)*exec_time) / CLOCKS_PER_SEC * 1000);
    
    free(stack);
    return best_profit;
}

// 生成随机物品
Item* generate_items(int n) {
    Item *items = (Item *)malloc(n * sizeof(Item));
    for (int i = 0; i < n; i++) {
        items[i].id = i + 1;
        items[i].weight = rand() % 100 + 1; // 1-100的随机重量
        items[i].value = rand() % 901 + 100; // 100-1000的随机价值
    }
    return items;
}

// 复制物品数组
Item* copy_items(Item *src, int n) {
    Item *dst = (Item *)malloc(n * sizeof(Item));
    memcpy(dst, src, n * sizeof(Item));
    return dst;
}

// 写入结果到文件
void write_results_to_file(const char *filename, int n, int capacity, 
                          clock_t bf_time, clock_t dp_time, clock_t gr_time, clock_t bt_time,
                          long long dp_mem) {
    FILE *file = fopen(filename, "a");
    if (!file) {
        printf("无法打开文件 %s\n", filename);
        return;
    }
    
    fprintf(file, "%d,%d,%.2f,%.2f,%.2f,%.2f,%.2f\n", 
            n, capacity, 
            (double)bf_time / CLOCKS_PER_SEC * 1000,
            (double)dp_time / CLOCKS_PER_SEC * 1000,
            (double)gr_time / CLOCKS_PER_SEC * 1000,
            (double)bt_time / CLOCKS_PER_SEC * 1000,
            (double)dp_mem / (1024 * 1024));
    
    fclose(file);
}

// 写入物品统计信息到文件
void write_items_to_file(const char *filename, Item *items, int n) {
    FILE *file = fopen(filename, "w");
    if (!file) {
        printf("无法打开文件 %s\n", filename);
        return;
    }
    
    fprintf(file, "物品编号,物品重量,物品价值\n");
    for (int i = 0; i < n; i++) {
        fprintf(file, "%d,%d,%.2f\n", items[i].id, items[i].weight, items[i].value);
    }
    
    fclose(file);
}

int main(int argc, char *argv[]) {
    // 设置控制台输出为UTF-8编码
    SetConsoleOutputCP(65001);
    // 设置随机数种子
    srand(time(NULL));

    // 解析命令行参数
    int run_brute_force = 1;
    int run_greedy = 1;
    int run_all = 1;
    
    if (argc > 1) {
        run_all = 0;
        run_brute_force = 0;
        run_greedy = 0;
        
        for (int i = 1; i < argc; i++) {
            if (strcmp(argv[i], "-bf") == 0) {
                run_brute_force = 1;
            } else if (strcmp(argv[i], "-gr") == 0) {
                run_greedy = 1;
            } else if (strcmp(argv[i], "-all") == 0) {
                run_all = 1;
            }
        }
    }
    
    // 记录程序开始时间(Windows高精度计时和系统时间)
    LARGE_INTEGER frequency, start_time, end_time;
    QueryPerformanceFrequency(&frequency);
    QueryPerformanceCounter(&start_time);
    SYSTEMTIME sys_start_time;
    GetLocalTime(&sys_start_time);
    printf("\n程序开始时间: %04d-%02d-%02d %02d:%02d:%02d.%03d\n",
           sys_start_time.wYear, sys_start_time.wMonth, sys_start_time.wDay,
           sys_start_time.wHour, sys_start_time.wMinute, sys_start_time.wSecond,
           sys_start_time.wMilliseconds);
    
    // 定义测试参数（严格按照要求）
    int item_counts[] = {1000, 2000, 3000, 4000, 5000, 6000, 7000, 8000, 9000, 10000, 20000, 40000, 80000, 160000, 320000};
    int capacities[] = {10000, 100000, 1000000};
    int num_item_counts = sizeof(item_counts) / sizeof(item_counts[0]);
    int num_capacities = sizeof(capacities) / sizeof(capacities[0]);
    
    // 创建结果文件(使用绝对路径)
    const char *results_file = "D:/suanfa/bao/knapsack_results.csv";
    FILE *file = fopen(results_file, "w");
    if (!file) {
        printf("错误: 无法创建结果文件 %s\n", results_file);
        return 1;
    }
    fprintf(file, "物品数量,背包容量,蛮力法时间(ms),动态规划时间(ms),贪心法时间(ms),回溯法时间(ms),动态规划内存(MB)\n");
    fclose(file);
    
    // 对每个物品数量和背包容量组合进行测试
    for (int c_idx = 0; c_idx < num_capacities; c_idx++) {
        int capacity = capacities[c_idx];
        printf("===== 背包容量 = %d =====\n", capacity);
        
        for (int n_idx = 0; n_idx < num_item_counts; n_idx++) {
            int n = item_counts[n_idx];
            printf("\n--- 物品数量 = %d ---\n", n);
            
            // 生成随机物品
            Item *items = generate_items(n);
            
            // 对n=1000的情况，保存物品统计信息
            if (n == 1000) {
                char items_file[50];
                sprintf(items_file, "items_n1000_c%d.csv", capacity);
                write_items_to_file(items_file, items, n);
            }
            
            // 复制物品数组用于每种算法
            Item *bf_items = copy_items(items, n);
            Item *dp_items = copy_items(items, n);
            Item *gr_items = copy_items(items, n);
            Item *bt_items = copy_items(items, n);
            
            clock_t bf_time = 0, dp_time = 0, gr_time = 0, bt_time = 0;
            long long dp_mem = 0;
            
            // 测试各种算法
            if (run_all || run_brute_force) {
                printf("\n===== 蛮力法 =====\n");
                if (n <= 1000) { // 适当放宽蛮力法的规模限制
                    brute_force(n, capacity, bf_items, &bf_time);
                } else {
                    printf("物品数量太大，跳过蛮力法\n");
                    bf_time = -1;
                }
            } else {
                bf_time = -1;
            }
            
            printf("\n===== 动态规划法 =====\n");
            if (n <= 320000 && capacity <= 1000000) { // 放宽动态规划的规模限制
                dynamic_programming(n, capacity, dp_items, &dp_time, &dp_mem);
            } else {
                printf("规模太大，跳过动态规划法\n");
                dp_time = -1;
                dp_mem = -1;
            }
            
            if (run_all || run_greedy) {
                printf("\n===== 贪心法 =====\n");
                greedy(n, capacity, gr_items, &gr_time);
            } else {
                gr_time = -1;
            }
            
            printf("\n===== 回溯法 =====\n");
            if (n <= 320000) { // 放宽回溯法的规模限制
                bt_time = backtracking(n, capacity, bt_items, &bt_time);
            } else {
                printf("规模太大，跳过回溯法\n");
                bt_time = -1;
            }
            
            // 写入结果到文件
            write_results_to_file(results_file, n, capacity, bf_time, dp_time, gr_time, bt_time, dp_mem);
            
            // 释放内存
            free(items);
            free(bf_items);
            free(dp_items);
            free(gr_items);
            free(bt_items);
        }
    }
    
    printf("\n结果已保存到 %s\n", results_file);
    
    // 记录程序结束时间并计算总执行时间(毫秒)
    QueryPerformanceCounter(&end_time);
    SYSTEMTIME sys_end_time;
    GetLocalTime(&sys_end_time);
    double total_time = (double)(end_time.QuadPart - start_time.QuadPart) * 1000.0 / frequency.QuadPart;
    
    printf("\n程序结束时间: %04d-%02d-%02d %02d:%02d:%02d.%03d\n",
           sys_end_time.wYear, sys_end_time.wMonth, sys_end_time.wDay,
           sys_end_time.wHour, sys_end_time.wMinute, sys_end_time.wSecond,
           sys_end_time.wMilliseconds);
    printf("程序总执行时间: %.2f ms\n", total_time);
    
    return 0;
}
